{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Playing Bluff\n",
    "## Problem definition\n",
    "Two students of EDEM, Jaime and Lucas, are playing a game named Bluff, that goes as follows. Jaime writes a number on a piece of paper. Without showing Lucas what he has written, he tells him what he wrote. Jaime might be lying or telling the truth. Then Lucas must guess if Jaime is lying or telling the truth, or he can choose to pass and not to continue playing. If Lucas discovers that Jaime lied, Jaime must pay Lucas €50. If Lucas wrongly accuses Jaime of lying, Lucas pays him €25. If Jaime told the truth and Lucas guesses this, then Jaime pays Lucas €5. If Jaime lied and Lucas does not guess that he lied, then Lucas pays Jaime €24. Should Lucas decide to pass, then neither player wins or loses anything.\n",
    "\n",
    "**a** Consider this a 2-player’s zero-sum game in game theory and write down the tabular representation.\n",
    "Let us note Jaime as player A and Lucas as player B. The game can be represented through the following matrix:\n",
    "\n",
    "| Player  B <br> Player A | Player A lied | Player A told truth | Pass |\n",
    "|-------------------------|---------------|---------------------|------|\n",
    "| lie                     | -50           | 24                  | 0    |\n",
    "| Tell the truth          | 25            | -5                  | 0    |\n",
    "\n",
    "\n",
    "**b** How would you determine the game mean value and the mixed strategies of both players in this case?\n",
    "\n",
    "Since this is a 2x3 game, let us formulate a Continuous Linear Programming problem to find the mixed strategies and the game mean value with these strategies.\n",
    "\n",
    "\n",
    "\n",
    "**c** Using the method seen in class to calculate the mixed strategies, a solver provides the following solution for Lucas (u1=0, u2=0, u3=0.02), where u1 is the decision variable associated to the alternative “Jaime lied”, u2 the decision variable associated to the alternative “Jaime told the truth” and u3 the decision variable associated to “Pass”. Write down the model and determine his optimal strategy.\n",
    "First, let us add a constant K to the game such that game values are non-negative:\n",
    "\n",
    "K = -50 yields\n",
    "\n",
    "|      Player  B <br> Player A        | Player A lied | Player A told truth | Pass |\n",
    "|-------------------------------------|------|------------|----|\n",
    "|    lie         |  0   |   74         |   50  |\n",
    "| Tell the truth |   75   |   45         |   50  |\n",
    "\n",
    "Now, for problem A, the CLP: \n",
    "\n",
    "$\\min z = x_1 + x_2$\n",
    "\n",
    "$s.t$\n",
    "\n",
    "$0*x_1 + 75*x_2 \\geq 1$\n",
    "\n",
    "$74*x_1 + 45*x_2 \\geq 1$\n",
    "\n",
    "$50*x_1 + 50*x_2 \\geq 1$\n",
    "   \n",
    "can be used to calculate the optimal strategies for player A. Once we obtain the values, the probabilities that define the optimal strategy for player A are defined a \n",
    "\n",
    "$p_1 = \\frac{x_1}{x_1+x_2}$\n",
    "\n",
    "$p_2 = \\frac{x_2}{x_1+x_2}$\n",
    "\n",
    "And the mean game value is: \n",
    "\n",
    "$z = \\frac{1}{x_1 + x_2} - 50$\n",
    "\n",
    "The optimal strategy for Player B can be obtained from the dual problem: \n",
    "\n",
    "$\\max z = u_1 + u_2 + u_3$\n",
    "\n",
    "$s.t$\n",
    "\n",
    "$0*u_1 + 74*u_2 + 50*u_3 \\leq 1$\n",
    "\n",
    "$75*x_1 + 45*u_2 + 50*u_3 \\leq 1$\n",
    "\n",
    "In this case the probabilities are given by:\n",
    "\n",
    "$q_1 = \\Large \\frac{u_1}{u_1+u_2+u_3}$\n",
    "\n",
    "$q_2 = \\Large \\frac{u_2}{u_1+u_2+u_3}$\n",
    "\n",
    "$q_3 = \\Large \\frac{u_3}{u_1+u_2+u_3}$\n",
    "\n",
    "The value of the objective value can also be computed from the decision variables of the dual as: \n",
    "\n",
    "$z = \\frac{1}{u_1 + u_2 + u_3} - 50$\n",
    "\n",
    "Now, plugin-in the values provided by the solver, we see that the optimal strategy for lucas is always to pass: \n",
    "\n",
    "$q_1 = \\Large \\frac{u_1}{u_1+u_2+u_3} = \\frac{0}{0 + 0 + 0.02} = 0$\n",
    "\n",
    "$q_2 = \\Large \\frac{u_2}{u_1+u_2+u_3} = \\frac{0}{0 + 0 + 0.02} = 0$\n",
    "\n",
    "$q_3 = \\Large \\frac{u_3}{u_1+u_2+u_3} = \\frac{0.02}{0 + 0 + 0.02} = 1$\n",
    "\n",
    "Also, the game value obtained is 0:\n",
    "\n",
    "$z = 1/0.02 - 50 = 0$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "source": [],
    "metadata": {
     "collapsed": false
    }
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}